package com.icbc.DataStructuresAndAlgorithms;

import org.junit.Test;

import java.math.BigInteger;
import java.util.Arrays;

/**
 * 递归解决八皇后/迷宫问题
 */
public class DiGuiDomo {
	private BigInteger big = new BigInteger("0");
	private BigInteger big1 = new BigInteger("1");
	public static void main(String[] args) {
		DiGuiDomo d = new DiGuiDomo();
		int num = d.jiecheng(10);
		System.out.println(num);
		System.out.println("=========wang========");
		d.hannuota(64, "a", "b", "c");
		System.out.println(d.big);
	}
	
	public int jiecheng(int a){
		if (a == 1) {
			return 1;
		} else {
			return jiecheng(a - 1) * a;
		}
	}
	
	@Test
	public void test(){
		int s = 1;
		for (int a = 1 ; a < 10 ; a++){
			s *= a;
		}
		System.out.println(s);
	}
	
	public void hannuota(int n,String a,String b,String c){
		if (n == 1){
			//System.out.println(a + " -> "  + c);
			big.add(big1);
		} else {
			hannuota(n - 1, a, c, b);
			//System.out.println(a + " -> " + c);
			big.add(big1);
			hannuota(n - 1, b, a, c);
		}
	}
	
	/**
	 * 理解:在汉诺塔中当要挪动n个盘子时,可简单理解先考虑1个盘子,只有一个盘子时,这个盘子就是最底下最大的盘子,
	 * 将它挪到c处即可,若是两个盘子呢?也是一样的道理将最下面和上面的部分分开,最底下的盘子最直接,直接挪到c处即可,但
	 * 最大的上面有盘子,那就需要将他们挪开,但挪开后最大的盘子要放在c处,那上面的盘子就只能放在b处,等大盘子挪过去后,
	 * 在将b柱上的盘子挪到c处,n个盘子也是一样的道理
	 *
	 * 深入理解代码执行:假设有4/(n)个盘子,我们看代码可以知道,当传入大于一个盘子时,就进入了else中,但else中第一行就是将b和c位置互换盘子减1后递归(第一层递归),再走发现
	 * 递归后仍是大于1的话就再次减1递归(第二层递归),直到n为1时仅表示不会再产生下一级递归并打印步骤,也就是最上面一个盘子的移动情况,但这时已经产生了3/(n-1)层递归,
	 * 且第3/(n-1)层递归仍未执行完毕,打印结束后回到了3/(第n-1层递归)代码1处,紧跟着的步骤意思就类似于上面说的,将最上面的盘子看做一个整体,移动到b上
	 * 将大的盘子移动到c上,打印a -> c步骤后,又再次进行了递归,注意:这里的递归是在上面说的第3(n-1层递归)层再次进行的递归是属于3/(n-1)层递归下的第一层递归,
	 * 递归后将a与b的位置互换在3(n-1)层盘子的基础上减1递归,由于在上面a的位置始终是没有变的,这里将ab互换递归后n为1进入if进行打印,这里是为了
	 * 将b上的盘子放到c上,第3(n-1)层递归结束,回到了第2(n-2)层代码1处,继续向下打印,这里的意思是:a为来源柱,c为目标柱,所以将a移动到c,但c是变化的,此时的c其实是b
	 * 将第3的大盘子放在了目标柱上,紧跟着又再次递归类似于将ab柱的功能互换,由于递归后bc的互换,认为c为来源柱,b为目标柱,a为中间柱,要将c上的盘子挪动到b上,在递归时再次进入代码1的递归
	 * 重复上面类似两个盘子的移动,而两个盘子有简化为1个盘子的移动
	 *
	 * 此代码是将盘子的移动简化为两个盘子的移动,代码1是为了将a移动到b上,然后将a移动到c,最后将b上的盘子移动到c上,多个盘子时也是通过递归的
	 * 不断简化来减少盘子最终变成两个盘子的问题,两个盘子在变成一个盘子的移动,在这个过程中abc三个柱的功能也在不断的转变
	 * @param n	表示多少个盘子
	 * @param a	A柱是原始的盘子
	 * @param b	B柱是中间柱
	 * @param c	C是目标柱
	 */
	public void han(int n,String a,String b,String c){
		if (n==1){
			System.out.println(a + " -> " + c);
		} else {
			/*
			* 在这里就类似上面说的将n个盘子无限的去分割,直到2个盘子的问题,
			* 将上面的盘子通过c放在b上,2个盘子过后,当挪动第三个盘子时,还是一样
			* 将上面的两个盘子看成一个盘子进行挪动,以此类推
			*/
			han(n-1, a, c, b);				//  <- 代码1
			/*再将大的盘子放到c上*/
			System.out.println(a + " -> " + c);		//  <- 代码2
			/*这里是在将b上面的盘子通过a放在c上*/
			han(n-1, b, a, c);				//  <- 代码3
		}
	}
}

//迷宫回溯问题
class MiGong{
	public static void main(String[] args) {
		// 先创建一个二维数组，模拟迷宫
		// 地图
		int[][] map = new int[8][7];
		// 使用1 表示墙
		// 上下全部置为1
		for (int i = 0; i < 7; i++) {
			map[0][i] = 1;
			map[7][i] = 1;
		}
		
		// 左右全部置为1
		for (int i = 0; i < 8; i++) {
			map[i][0] = 1;
			map[i][6] = 1;
		}
		//设置挡板, 1 表示
		map[3][1] = 1;
		map[3][2] = 1;
//        map[1][2] = 1;
//        map[2][2] = 1;
		
		// 输出地图
		System.out.println("地图的情况");
		for (int i = 0; i < 8; i++) {
			for (int j = 0; j < 7; j++) {
				System.out.print(map[i][j] + " ");
			}
			System.out.println();
		}
		
		//使用递归回溯给小球找路
		setWay(map, 1, 1);
		//setWay2(map, 1, 1);
		
		//输出新的地图, 小球走过，并标识过的递归
		System.out.println("小球走过，并标识过的 地图的情况");
		for (int i = 0; i < 8; i++) {
			for (int j = 0; j < 7; j++) {
				System.out.print(map[i][j] + " ");
			}
			System.out.println();
		}
		
	}
	
	//使用递归回溯来给小球找路
	//说明
	//1. map 表示地图
	//2. i,j 表示从地图的哪个位置开始出发 (1,1)
	//3. 如果小球能到 map[6][5] 位置，则说明通路找到.
	//4. 约定： 当map[i][j] 为 0 表示该点没有走过 当为 1 表示墙  ； 2 表示通路可以走 ； 3 表示该点已经走过，但是走不通
	//5. 在走迷宫时，需要确定一个策略(方法) 下->右->上->左 , 如果该点走不通，再回溯
	/*此代码的回溯原理:当向下移动时是递归调用(第一层递归),就会再次执行代码,进入else的判断中,发现此节点值为0那么就会按照策略进行移动,
	* 先向下递归(第二层递归)发现向下的节点值不是0,返回false,当前的递归结束(第二层向下的递归结束),
	* 回到上层的递归(回到了第一层判断向下的if处,由于返回false),继续判断else if向右进入递归(进入第二层向右的递归),
	* 发现此节点值不为0返回false,回到上层的递归(结束第二层向右的递归,回到第一层),
	* 继续判断,都为false时(向下,向右,向上,向左的递归都返回了false,回到了第一层),由于他们判断都为false则第一层进入else中,
	* 将当前节点值改为3,返回false,回到第一层的上一层递归处,上一层再继续它的向右向左向上的递归,若有通路则改为2,一旦不通同样改为3,
	* 将结果false返回到上一层的上一层递归处
	*/
	/**
	 *
	 * @param map 表示地图
	 * @param i 从哪个位置开始找
	 * @param j
	 * @return 如果找到通路，就返回true, 否则返回false
	 */
	public static boolean setWay(int[][] map, int i, int j) {
		if(map[6][5] == 2) { // 通路已经找到ok
			return true;
		} else {
			if(map[i][j] == 0) { //如果当前这个点还没有走过
				//按照策略 下->右->上->左  走
				map[i][j] = 2; // 假定该点是可以走通.
				if(setWay(map, i+1, j)) {//向下走
					return true;
				} else if (setWay(map, i, j+1)) { //向右走
					return true;
				} else if (setWay(map, i-1, j)) { //向上
					return true;
				} else if (setWay(map, i, j-1)){ // 向左走
					return true;
				} else {
					//说明该点是走不通，是死路
					map[i][j] = 3;
					return false;
				}
			} else { // 如果map[i][j] != 0 , 可能是 1， 2， 3
				return false;
			}
		}
	}
}

//八皇后问题(递归回溯算法)
class Queue8 {
	
	//定义一个max表示共有多少个皇后
	int max = 8;
	//定义数组array, 保存皇后放置位置的结果,比如 arr = {0 , 4, 7, 5, 2, 6, 1, 3}
	int[] array = new int[max];
	static int count = 0;
	static int judgeCount = 0;
	public static void main(String[] args) {
		//测试一把 ， 8皇后是否正确
		Queue8 queue8 = new Queue8();
		queue8.check(0);
		System.out.printf("一共有%d解法", count);
		System.out.printf("一共判断冲突的次数%d次", judgeCount); // 1.5w
		
	}
	
	//编写一个方法，放置第n个皇后
	//特别注意： check 是 每一次递归时，进入到check中都有  for(int i = 0; i < max; i++)，因此会有回溯
	private void check(int n) {
		//这里判断的意思是由于n是从0开始的,当n == 8 时,其实放的是第9个皇后
		//表示8个换后已经放好了,没必要继续了
		if(n == max) {  //n = 8 , 其实8个皇后就既然放好
			print();
			return;
		}
		
		//这里的循环意思是,由于棋盘是8*8的棋盘,每一行放一个皇后,
		//在放第n个皇后时需要从这一行坐标为0的位置开始依次放置,最大到这行的尾端也就是7的位置,并判断是否与之前放置的皇后冲突
		//依次放入皇后，并判断是否冲突
		for(int i = 0; i < max; i++) {
			//先把当前行的这个皇后 n , 放到该行的第i列
			array[n] = i;
			//判断当放置第n个皇后到i列时，是否与之前放置的皇后冲突
			if(judge(n)) { // 不冲突
				//接着放n+1个皇后,即开始递归
				check(n+1); //
			}
			//如果冲突，就继续执行 array[n] = i; 即将第n个皇后，放置在本行得 后移的一个位置,
			/*注意:当此行每个位置放置的皇后都与前面的冲突时,则会循环结束且不会递归,这样就会方法结束回到上一层
			递归处(也就是前一个皇后的摆放处),由于前面方法结束,也就证明此皇后放在这个位置不正确,则继续后移递归
			计算后面皇后的摆放;
			当8个皇后摆放完毕时由于上面if判断的是n == 8进行return,就相当于此路不通一样,继而继续循环进行另外一种8皇后摆放方式
			且是优先挪动最后放置的皇后,又由于是for循环从当前行的0位置顺序依次到7的位置放置,那么新得出的结果必然不会与之前的结果重复*/
		}
	}
	
	//查看当我们放置第n个皇后, 就去检测该皇后是否和前面已经摆放的皇后冲突
	/**
	 *
	 * @param n 表示第n个皇后 ,这里的n是从0开始
	 * @return
	 */
	private boolean judge(int n) {
		judgeCount++;
		for(int i = 0; i < n; i++) {
			// 说明
			//1. array[i] == array[n]  表示判断 第n个皇后是否和前面的n-1个皇后在同一列
			//2. Math.abs(n-i) == Math.abs(array[n] - array[i]) 表示判断第n个皇后是否和第i皇后是否在同一斜线
			//由于是斜线关系,那么冲突的两个皇后x轴和y轴相减绝对值必然是相等的
			// n = 1  放置第 2列 1 n = 1 array[1] = 1
			// Math.abs(1-0) == 1  Math.abs(array[n] - array[i]) = Math.abs(1-0) = 1
			//3. 判断是否在同一行, 没有必要，n 每次都在递增
			if(array[i] == array[n] || Math.abs(n-i) == Math.abs(array[n] - array[i]) ) {
				return false;
			}
		}
		return true;
	}
	
	//写一个方法，可以将皇后摆放的位置输出
	private void print() {
		count++;
		for (int i = 0; i < array.length; i++) {
			System.out.print(array[i] + " ");
		}
		System.out.println();
	}
}

class huanghou8{
	int[] arr = new int[8];
	int count = 0;
	public static void main(String[] args) {
		huanghou8 huanghou8 = new huanghou8();
		huanghou8.zoupan(0);
		System.out.println(huanghou8.count);
	}
	
	//走盘
	public void zoupan(int n){
		if (n == 8){
			count++;
			print();
			return;
		}
		
		for(int a = 0; a < 8 ; a ++){
			arr[n] = a;
			if (!chongtu(n)){
				zoupan(n + 1);
			}
		}
	}
	
	//打印
	public void print(){
		for (int i = 0; i < arr.length; i++) {
			int i1 = arr[i];
			System.out.print(i1 + " ");
		}
		System.out.println();
	}
	
	//冲突
	public boolean chongtu(int n){
		boolean flag = false;
		for (int a = 0 ; a < n ; a ++ ){
			if (arr[n] == arr[a] || Math.abs(arr[n] - arr[a]) == Math.abs(n-a) ){
				flag = true;
			}
		}
		return flag;
	}
}

class count{
	@Test
	public void test(){
	
	}
	
	/**
	 * 计算不重复数据s数组中n个数之和为sum的所有可能
	 * 如 : 1~9的数组,求3个数和为15的所有可能
	 * @param s     s为目标数组,数组中为不重复数据
	 * @param sum   sum为n个数之和的要求
	 * @param num   num个数
	 */
	public void test(int[] s,int sum,int num){
		int[] cache = new int[num];
		test1(cache,s,0,0,sum,num - 1);
	}
	
	/*
	 * 思路 : 假设要得到数组1~9的中3个数之和为15的所有可能,
	 *      常规想法是3层循环1 + 2 + (3~9)然后1 + 3 + (4~9) ...
	 *      一直到7 + 8 + 9结束,统计在循环中得到的所有和为15的数据
	 *      但如果是1~25的数组求5个数之和为65的所有可能呢?
	 *      此时就需要5层循环了,这是有规律可循的,而且随着要求n个数之和为sum就需要有n层循环
	 *      此时我们就需要使用递归了;
	 * 以1~9的数组中求3个数之和为15的所有可能为例 :
	 *      当进入第一层循环时,我们来进行控制也就是第一个数字走到1时,我们来进行
	 *      递归进入第二层,还是一个循环,但这个循环是从2开始,在开始循环时再次进入第三层的递归,
	 *      第三层递归从3开始循环,但是到第三层递归时就不再进行递归了,而且当第三层递归结束回到
	 *      第二层递归时,2 -> 3后,又再次进去了第三层递归,依次类推
	 * 根据以上分析,我们需要有一个原数组s,
	 * 还需要有一个记录我们选中数字的中间数组cache,使用中间缓存数组可以方便我们计算选中的3个数之和是否是15,
	 * 还需要一个记录循环开始的标识pre,pre是标识当前层循环应该从pre开始循环
	 * 还需要一个记录当前是第几层递归的标识n,以及最多几层递归的num,和要求的和sum
	 *
	 * cache为缓存数组,里面有3个数,计算cache中数据之和是否为sum,是sum时cache中的数就是结果
	 * s为原数组,即1~9的数组
	 * pre表示当前循环从pre开始循环
	 * n表示当前递归的层数
	 * sum为num个数之和
	 * num表示需要从s数组中取num个数,这num个数之和为sum,num在传入时进行了 - 1
	 */
	public void test1(int[] cache,int[] s,int pre,int n,int sum,int num){
		//开始时一个循环,因为正常逻辑也是开始就是循环,只是根据要求的数量不同在其内部生成多个循环
		for (int a = pre; a < s.length ; a++) {
			//记录当前层的循环到的数据,如第一层cache[0] = s[0],n标识第几层递归从0开始,第3层n刚好为2
			cache[n] = s[a];
			//这里标记当n >= num时就不再递归,这里控制递归的层级,
			//也就是说在第一层循环和第二层循环时需要递归,但进入第三层循环时它是不可以递归的
			if (n < num) {
				//将cache和原数组s传入
				//将循环的开始位置 + 1,表示下一层循环从2开始
				//层数n + 1,表示进入下一层递归,将sum和num传入
				test1(cache,s,a + 1,n + 1,sum,num);
			}
			//当cache中的数据之和为sum并且当前递归层级为num时,也就是处于第三层的递归时
			//cache中的数据才是我们需要的数据
			if (sum(cache) == sum && n == num) {
				print(cache);
				break;
			}
		}
	}
	
	//得到cache数组所有元素的和
	public int sum(int[] cache){
		return Arrays.stream(cache).sum();
	}
	
	//打印cache数组
	public void print(int[] cache){
		Arrays.stream(cache).forEach(a -> System.out.print(a+" "));
		System.out.println();
	}
}
